1. Field of the Invention
The present invention relates generally to lossless data compression, and more specifically to a system and method providing for lossless compression of a two-dimensional array of data.
2. Description of Related Art
The quality of a digital image is a function of its resolution, which is a function of the number of pixels in the image array, and is also a function of the intensity range used to define each pixel position. Gray-scale images are considered as two-dimensional arrays of intensity values, digitized to some number of bits. Color images are usually represented in some color space (e.g., RGB, YUV, LAB), in which each component is a gray-scale image. In a typical high quality image system, 24 bits per pixel are used to display color and intensity variations. As the number of pixels increases, the resolution of the image increases. Also, as the intensity range used to define each pixel position increases, the quality of the image is enhanced. However, as resolution and intensity range increases, the amount of image data required to store or transmit the image increases proportionally. In order to reduce the number of digital bits required to store and/or transmit an image, compression is often performed.
Data compression refers to the temporary coding of data in a way that saves storage space or transmission time. The main objective of image data compression is to maximize picture quality while minimizing the amount of data required per pixel. Many different types of data compression techniques are known for reducing the number of bits required to represent information in data transmission or storage, thereby conserving bandwidth and/or memory.
Image compression algorithms are broadly classified into lossy (irreversible) schemes, for which the original pixel intensities cannot be perfectly recovered from the encoded bit stream, and lossless (reversible) schemes for which the coding algorithms yield decompressed images identical to the original digitized images. In general, lossless compression is required in applications where the images are subjected to further processing, e.g. for the purpose of extraction of specific information. Lossless compression is generally the choice also for images obtained at great cost, for which it may be unwise to discard any information that later may be found to be necessary, or in applications where the desired quality of the rendered image is unknown at the time of acquisition, as may be the case in digital photography. In addition, lossless compression may be preferred over lossy compression for applications where intensive editing or repeated compression/decompression is required as the accumulation of error due to a lossy iteration may become unacceptable. One particular field of application for lossless image data compression techniques is in computer generated imagery for motion pictures. Examples of lossless image data compression formats include RLA encoding used to generate Wavefront raster image files, and LZW encoding used for GIF files.
In general, data compression algorithms are based on the simple idea of mapping the representation of data from one group of symbols to another more concise series of symbols. Two schemes form the basis of many of the data compression algorithms currently known in the art. These are Huffman coding and LZW (for Lempel and Ziv, its creators, and Welch, who made substantial contributions) coding. Both Huffman and LZW coding are lossless compression techniques. Huffman coding reduces the number of bits used to represent characters that occur frequently in the data and increases the number of bits for characters that occur infrequently. The LZW method, on the other hand, encodes strings of characters, using the input data to build an expanded alphabet based on the strings that it sees. These two different approaches both work by reducing redundant information in the input data. Compression by Huffman coding requires that the compressor know or learn the probabilities of each type of data to compress. In order to learn the probabilities, Huffman coding performs two passes over the data requiring temporary storage of the entire data block, which is memory intensive especially for large databases. LZW, on the other hand, works by extending the alphabet using the additional characters to represent strings of regular characters. The key to the algorithm is the establishment of a table that matches character strings with code words representing strings. This table must exist as an index for translating between the stored or transmitted code and the original symbol. The use of such a table is also memory intensive.
Important performance parameters for compressed encoding processes include: speed of compression which is a function of the number of processing instructions required to be executed in order to generate the compressed data; and compression ratio which is defined by the size of an uncompressed data file divided by the size of the compressed version, expressing the degree to which a compression algorithm can reduce file size. There is an ever increasing demand for improved compressed encoding processes providing higher speeds of compression and higher compression ratios.
What is needed is an improved system and method for compressing and decompressing image data wherein the system and method provides a higher speed of compression and a higher compression ratio than prior art compression systems.